#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>


void Swap(int* a, int* b) 
{
    int tmp = *b;
    *b = *a;
    *a = tmp;
}

void Max(int a[], int start, int end)
{
    int dad = start;
    int son = dad * 2 + 1;

    while (son <= end) 
    { 
        if (son + 1 <= end && a[son] < a[son + 1]) 
        {
            son++;
        }
        if (a[dad] > a[son]) 
        {
            return;
        }
        else 
        {
            Swap(&a[dad], &a[son]);
            dad = son;
            son = dad * 2 + 1;
        }
    }
}
void HeapSort(int a[], int n)
{
    int i = 0;

    for (i = n / 2 - 1; i >= 0; i--)
    {
        Max(a, i, n - 1);
    }

    for (i = n - 1; i > 0; i--)
    {
        Swap(&a[0], &a[i]);
        Max(a, 0, i - 1);
    }
}

int main() 
{
    int a[] = { 3,6,8,1,4,2,5,7,9 };
    int n = (int)sizeof(a) / sizeof(*a);
    HeapSort(a, n);
    int i = 0;
    for (i = 0; i < n; i++)
    {
        printf("%d ", a[i]);
    }
    return 0;
}